package lanqiao.真题.第13届决赛JavaB组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 【问题描述】
 * 任何一个大于1的正整数都能被分解为若干个质数相乘，比如28=2×2×7
 * 被分解为了三个质数相乘。请问在区间[2333333,23333333]中有多少个正整数
 * 可以被分解为12个质数相乘？
 * 【答案提交】
 * 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
 * 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
 * @since 2023-05-16 22:48
 */
public class B_数数 {
}
class MainB{
    static List<Integer> all = new ArrayList<>();
    static {    
        //把所有可能用到的质数算出保存
        int max = 23333;
        int cur = 2;
        while(cur <= max){
            if(check(cur)) {
                all.add(cur);
            }
            cur++;
        }
    }
    static int getCnt(int num){
        int cur = 0;
        int cnt = 0;
        while(num > 1){
            if(num % all.get(cur) == 0){
                num /= all.get(cur);
                cnt++;
            }else{
                cur++;
                //2^10 * 23333
                if(cur >= all.size()) return 0;//不符合情况
            }
        }
        return cnt;
    }
    public static void main(String[] args) {
//        System.out.println(all);
        int res = 0;
        /*
        12 个质数乘积
        假如最后一个质数很大，乘积会大于23333333
        2^11 = 2048
        这个最大质数不会超过23333，先把所有可能用到的质数算出保存
         */
        for(int i = 2333333; i <= 23333333; i++){
            if(getCnt(i) == 12){
                System.out.println(i);
                res++;
            }
        }
        //25606
        System.out.println(res);
    }

    private static boolean check(int num){
        for(int i = 2; i < num; i++){
            if(num % i == 0) return false;
        }
        return true;
    }

}
